<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Weight Constraints
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial076.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial070.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial078.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc148">10.7</A>&nbsp;&nbsp;Weight Constraints</H2>
<A NAME="weight-constraint"></A>
<A NAME="@default283"></A>

<A NAME="@default284"></A>
<A NAME="@default285"></A>
Another constraint between sets and integers is the weight/3 constraint.
It allows the association of weights to set elements, and can help when
solving problems of the knapsack or bin packing type.
The constraint takes a set and an array of element weights and
constrains the weight of the whole set:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- ic_sets:(Container :: [] .. [1, 2, 3, 4, 5]),
   Weights = [](20, 34, 9, 12, 19),
   weight(Container, Weights, W).
Container = Container{([] .. [1, 2, 3, 4, 5]) : _2127{0 .. 5}}
Weights = [](20, 34, 9, 12, 19)
W = W{0 .. 94}
There is 1 delayed goal.
Yes (0.01s cpu)
</PRE></BLOCKQUOTE>
By adding a capacity limit and a search primitive, we can solve a
knapsack problem:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- ic_sets:(Container :: [] .. [1, 2, 3, 4, 5]),
   Weights = [](20, 34, 9, 12, 19),
   weight(Container, Weights, W),
   W #=&lt; 50,
   insetdomain(Container,_,_,_).
Weights = [](20, 34, 9, 12, 19)
W = 41
Container = [1, 3, 4]
More (0.00s cpu)
</PRE></BLOCKQUOTE>
By using the heuristic options provided by insetdomain, we can
implement a greedy heuristic, which finds the optimal solution
(in terms of greatest weight) straight away:
<A NAME="@default286"></A>
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- ic_sets:(Container :: [] .. [1, 2, 3, 4, 5]),
   Weights = [](20, 34, 9, 12, 19),
   weight(Container, Weights, W),
   W #=&lt; 50,
   insetdomain(Container,decreasing,heavy_first(Weights),_).
W = 48
Container = [1, 3, 5]
Weights = [](20, 34, 9, 12, 19)
More (0.00s cpu)
</PRE></BLOCKQUOTE>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<A HREF="../bips/lib/ic_sets/weight-3.html"><B>weight(?Set, ++ElementWeights, ?Weight)</B></A><A NAME="@default287"></A><DD CLASS="dd-description">
 According to the array of element weights, the weight of set Set1 is Weight 
</DL>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 10.5: Set Weight Constraint</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial076.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial070.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial078.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
